package algorithm_demo.demo05;

/**
 * 从左到右的尝试模型
 * 给定两个长度为N的数组weights和values，weights[i]和values[i]分别代表i号物品的重量和价值
 * 给定一个正数bag，表示一个载重bag的袋子
 * 你装的物品不能超过这个重量，返回你能装下最多的价值是多少
 *
 * @author Api
 * @date 2023/3/6 23:34
 */
public class Code06_Knapsack1 {
    /*暴力递归*/
    public static int getMaxValue1(int[] weights, int[] values, int bag) {
        return process1(weights, values, 0, bag);
    }

    /**
     * 递归函数
     *
     * @param weights 重量的数组
     * @param values  价值的数组
     * @param index   最大价值(0-N的)
     * @param rest    剩余空间
     * @return 不超重的情况下，能够得到的最大价值
     */
    public static int process1(int[] weights, int[] values, int index, int rest) {
        //已经装的重量大于包可承受的重量
        //base case1
        if (rest < 0) {
            return -1;
        }
        //index当前包的重量
        //base case2
        if (index == weights.length) {
            return 0;
        }
        int p1 = process1(weights, values, index + 1, rest);
        int p2Next = process1(weights, values, index + 1, rest - weights[index]);
        int p2 = -1;
        if (p2Next != -1) {
            p2 = values[index] + p2Next;
        }
        return Math.max(p1, p2);
    }

    public static void main(String[] args) {
        int[] weights = {6, 2, 3, 4, 12, 3, 4};
        int[] values = {2, 3, 2, 4, 1, 2, 43};
        int bag = 10;
        int maxWeight = getMaxValue1(weights, values, bag);
        int maxWeight1 = getMaxValue2(weights, values, bag);
        System.out.println(maxWeight);
        System.out.println(maxWeight1);
    }


    /*动态规划*/

    /**
     * 动态规划（如果从暴力递归修改为动态规划，取决于是暴力递归是否有重复性问题）
     *
     * @param weights 固定参数
     * @param values  固定参数
     * @param bag     固定参数
     * @return 返回背包最大价值
     */
    public static int getMaxValue2(int[] weights, int[] values, int bag) {
        return process2(weights, values, bag);
    }

    public static int process2(int[] weights, int[] values, int bag) {
        int N = weights.length;
        int[][] dp = new int[N + 1][bag + 1];
        //java默认二维数组全部为0，即db[N][...]均为0
        for (int index = N - 1; index >= 0; index--) {
            for (int rest = 0; rest <= bag; rest++) {
                int p1 = dp[index + 1][rest];
                int p2 = -1;
                if (rest - weights[index] >= 0) {
                    p2 = values[index] + dp[index + 1][rest - weights[index]];
                }
                dp[index][rest] = Math.max(p1, p2);
            }
        }
        return dp[0][bag];
    }
}
